Search for: All records

We give the first pseudorandom generators with sub-linear seed length for the following variants of read-once branching programs (roBPs): 1) First, we show there is an explicit PRG of seed length O(log²(n/ε)log(n)) fooling unbounded-width unordered permutation branching programs with a single accept state, where n is the length of the program. Previously, [Lee-Pyne-Vadhan RANDOM 2022] gave a PRG with seed length Ω(n) for this class. For the ordered case, [Hoza-Pyne-Vadhan ITCS 2021] gave a PRG with seed length Õ(log n ⋅ log 1/ε). 2) Second, we show there is an explicit PRG fooling unbounded-width unordered regular branching programs with a single accept state with seed length Õ(√{n ⋅ log 1/ε} log 1/ε). Previously, no non-trivial PRG (with seed length less than n) was known for this class (even in the ordered setting). For the ordered case, [Bogdanov-Hoza-Prakriya-Pyne CCC 2022] gave an HSG with seed length Õ(log n ⋅ log 1/ε). 3) Third, we show there is an explicit PRG fooling width w adaptive branching programs with seed length O(log n ⋅ log² (nw/ε)). Here, the branching program can choose an input bit to read depending on its current state, while it is guaranteed that on any input x ∈ {0,1}ⁿ, the branching program reads each input bit exactly once. Previously, no PRG with a non-trivial seed length is known for this class. We remark that there are some functions computable by constant-width adaptive branching programs but not by sub-exponential-width unordered branching programs. In terms of techniques, we indeed show that the Forbes-Kelley PRG (with the right parameters) from [Forbes-Kelley FOCS 2018] already fools all variants of roBPs above. Our proof adds several new ideas to the original analysis of Forbes-Kelly, and we believe it further demonstrates the versatility of the Forbes-Kelley PRG. 

We present new constructions of pseudorandom generators (PRGs) for two of the most widely studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth d∈N and n1+δ wires, where δ=2−O(d) , using seed length O(n1−δ) and with error 2−nδ . This tightly matches the best known lower bounds for this circuit class. As a consequence of our result, all the known hardness for LTF circuits has now effectively been translated into pseudorandomness. This brings the extensive effort in the last decade to construct PRGs and deterministic circuit-analysis algorithms for this class to the point where any subsequent improvement would yield breakthrough lower bounds. Our second contribution is a PRG for De Morgan formulas of size s whose seed length is s1/3+o(1)⋅polylog(1/ϵ) for error ϵ . In particular, our PRG can fool formulas of sub-cubic size s=n3−Ω(1) with an exponentially small error ϵ=exp(−nΩ(1)) . This significantly improves the inverse-polynomial error of the previous state-of-the-art for such formulas by Impagliazzo, Meka, and Zuckerman (FOCS 2012, JACM 2019), and again tightly matches the best currently-known lower bounds for this class. In both settings, a key ingredient in our constructions is a pseudorandom restriction procedure that has tiny failure probability, but simplifies the function to a non-natural “hybrid computational model” that combines several computational models.